package com.future;

import java.util.LinkedList;

/**
 * Description:
 * 实现一个基本的计算器来计算简单的表达式字符串。
 * <p>
 * 表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
 * <p>
 * 你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-231, 231 - 1] 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/8:22:46
 */
public class Solution_772 {

    public static void main(String[] args) {
        String s = "(2+6*3+5-(3*14/7+2)*5)+3";
        s = "2*(5+5*2)/3+(6/2+8)";
        //s = "(2+6*3+5-(3*14/7+2)*5)+3";
        s = "1*2-3/4+5*6-7*8+9/10";
        System.out.println(calculate(s));
    }

    public static int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] ans = process(s.toCharArray(), 0);
        return ans[0];
    }

    private static int[] process(char[] nums, int curIndex) {
        LinkedList<String> stack = new LinkedList<>();
        int curVal = 0;
        int[] tmpAns;
        int length = nums.length;
        char cha;
        int i = curIndex;
        while (i < length && (cha = nums[i]) != ')') {
            if (cha >= '0' || '9' <= cha) {
                curVal = (cha - '0') + 10 * curVal;
                i++;
            } else if (cha == '(') {
                // 右括号
                tmpAns = process(nums, i + 1);
                curVal = tmpAns[0];
                i = tmpAns[1] + 1;
            } else {
                // 运算符
                doAddStack(stack, curVal);
                stack.addLast(String.valueOf(cha));
                i++;
                curVal = 0;
            }
        }
        doAddStack(stack, curVal);
        return new int[]{doOperation(stack), i};
    }

    private static int doOperation(LinkedList<String> stack) {
        if (stack.isEmpty()) {
            return 0;
        }
        Integer ans = 0;
        boolean isAdd = true;
        while (!stack.isEmpty()) {
            String operate = stack.pollFirst();
            if ("-".equals(operate)) {
                isAdd = false;
            } else if ("+".equals(operate)) {
                isAdd = true;
            } else {
                if (isAdd) {
                    ans += Integer.parseInt(operate);
                } else {
                    ans -= Integer.parseInt(operate);
                }
            }
        }
        return ans;
    }

    private static void doAddStack(LinkedList<String> stack, int curVal) {
        if (stack.isEmpty()) {
            stack.add(String.valueOf(curVal));
            return;
        }
        String poll = stack.pollLast();
        if ("*".equals(poll) || "/".equals(poll)) {
            Integer pollVal = Integer.parseInt(stack.pollLast());
            curVal = poll.equals("*") ? pollVal * curVal : pollVal / curVal;
        } else {
            stack.addLast(poll);
        }
        stack.addLast(String.valueOf(curVal));
    }
}
